package tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Liangyaoyun
 */
public class BinaryTraversal {
    private static class Node{
        Object data;
        Node lChild;
        Node rChild;
    }
    /*
    * 二叉树的深度优先遍历
    * */
    public void preOrderTraversal(Node root){

        if (root==null){
            return;
        }
        //1.输出当前子树的根节点
        System.out.println(root.data);

        //2.对以当前节点左孩子为根的左子树进行先序深度优先遍历

        System.out.println(root.lChild);

        //3.对以当前节点左孩子为根的右子树进行先序深度优先遍历

        System.out.println(root.rChild);

    }
    //中序遍历
    public void middleOrderTraversal(Node root){
            if (root==null){
                return;
            }
            middleOrderTraversal(root.lChild);
            System.out.println(root.data);
            middleOrderTraversal(root.rChild);
        }
    //后序遍历
    public void postOrderTraversal(Node root){
        if (root==null){
            return;
        }
        preOrderTraversal(root.lChild);
        preOrderTraversal(root.rChild);
        System.out.println(root.data);
    }

    public void bfs(Node root){
        Queue<Node>queue=new LinkedList<>();

        queue.offer(root);
        while (!queue.isEmpty()){
            Node tmp= queue.poll();
            System.out.println(tmp.data);

            if (tmp.lChild!=null){
                queue.offer(tmp.lChild);
            }

            if (tmp.rChild!=null){
                queue.offer(tmp.rChild);
            }
            System.out.println();
        }
    }

}
